\chapter{How it works}

Eigenmath is written in the C programming language.
Its central data structure is
an array of 100 thousand blocks of memory.
The size of each block is 12 bytes for Mac OS X
and 16 bytes for Windows.
\begin{verbatim}
         _______
      0 |_______|  \
      1 |_______|   |
      2 |_______|   |
        |       |   |
        .       .   | 1,200,000 bytes (Mac OS X)
        .       .   |
        .       .   |
        |_______|   |
 99,999 |_______|  /
\end{verbatim}

\bigskip
\noindent
If necessary, Eigenmath will allocate additional memory in increments of
100 thousand blocks, up to a maximum of 10 million blocks
(one hundred times what is shown above).

%\begin{verbatim}
%100000 blocks (12 bytes/block)
%99706 free
%294 used
%\end{verbatim}

\newpage

\noindent
Blocks are C structs defined as follows.

\medskip
\begin{verbatim}
typedef struct U {
     union {
          struct {
               struct U *car;          // pointing down
               struct U *cdr;          // pointing right
          } cons;
          char *printname;
          char *str;
          struct tensor *tensor;
          struct {
               unsigned int *a, *b;    // rational number a over b
          } q;
          double d;
     } u;
     unsigned char k, tag;
} U;
\end{verbatim}

\medskip
\noindent
The member $k$ identifies the union that is stored in the block.
The value of $k$ is one of the following.

\medskip
\begin{verbatim}
enum {
        CONS,
        NUM,
        DOUBLE,
        STR,
        TENSOR,
        SYM,
};
\end{verbatim}

\newpage

\noindent
Blocks are linked together to store mathematical expressions.
For example, the following shows how the expression
$A\times B+C$ is stored.
\begin{verbatim}
 _______      _______                                _______
|CONS   |--->|CONS   |----------------------------->|CONS   |
|       |    |       |                              |       |
|_______|    |_______|                              |_______|
    |            |                                      |
 ___V___      ___V___      _______      _______      ___V___
|SYM    |    |CONS   |--->|CONS   |--->|CONS   |    |SYM    |
|add    |    |       |    |       |    |       |    |C      |
|_______|    |_______|    |_______|    |_______|    |_______|
                 |            |            |
              ___V___      ___V___      ___V___
             |SYM    |    |SYM    |    |SYM    |
             |times  |    |A      |    |B      |
             |_______|    |_______|    |_______|
\end{verbatim}

\bigskip
\noindent
Only CONS blocks contain pointers to other blocks.
Every other kind of block is a terminal node.
Fundamentally, this approach is a subset of the S-expression data structure
invented by John McCarthy for the LISP programming language.

\newpage

\noindent
Confining pointers to CONS blocks differs from the more traditional linked
list data structure in a significant way.
In a linked list, blocks contain both data and pointers simultaneously.
For example, this is how one might store $A+B$ using a linked list.
\begin{verbatim}
 _______       _______       _______
|_______|---->|_______|---->|_______|
|SYM    |     |SYM    |     |SYM    |
|add    |     |A      |     |B      |
|_______|     |_______|     |_______|
\end{verbatim}

\bigskip
\noindent
Now suppose we want to store an additional expression $A+C$.
Using a linked list, we have to make copies of the SYM-add and
SYM-A blocks
because of the pointers.
If we were to rewrite the pointers we would destroy the original
expression.
However, with S-expressions all we have to do is allocate new CONS
blocks to create new expressions.
We never have to copy data.
We can store thousands of expressions with CONS
blocks all pointing to a common SYM-A block.

\newpage

\noindent
As it runs, Eigenmath allocates memory blocks to build new expressions.
For example, $A+A$ is changed to $2A$ by $evel\_add$.
Here is the input expression to $eval\_add$.
\begin{verbatim}
 _______      _______      _______
|CONS   |--->|CONS   |--->|CONS   |
|       |    |       |    |       |
|_______|    |_______|    |_______|
    |            |            |
 ___V___         |         ___V___
|SYM    |        |------->|SYM    |
|add    |                 |A      |
|_______|                 |_______|
\end{verbatim}

\bigskip
\noindent
And here is the output expression from $eval\_add$.
\begin{verbatim}
 _______      _______      _______
|CONS   |--->|CONS   |--->|CONS   |
|       |    |       |    |       |
|_______|    |_______|    |_______|
    |            |            |
 ___V___      ___V___      ___V___
|SYM    |    |NUM    |    |SYM    |
|times  |    |2      |    |A      |
|_______|    |_______|    |_______|
\end{verbatim}

\bigskip
\noindent
The three CONS blocks in the output expression are new.
They are not the same as the CONS blocks in the input expression.
In this particular example, Eigenmath allocates a total of four blocks
to build the new expression,
three CONS blocks and one NUM block.
Eventually all of the available blocks get used up, at which point Eigenmath
does garbage collection to recover unused blocks.
Returning to the example, garbage collection would recover the original
three CONS blocks that formed $A+A$, if nothing points to that expression.
